package dynamic.subarrysubstring;

/**
 * @Classname : LongestValidParentheses
 * @Description : 32. 最长有效括号
 * https://leetcode.cn/problems/longest-valid-parentheses/
 * @Author : chentianyu
 * @Date 2023/3/9 21:02
 */


public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        int n = s.length(), longest = 0;
        int[] dp = new int[n + 1];  // dp[i] 表示以位置 i - 1 结尾的最长有效括号子串长度
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) == ')') {  // 有效括号子串必须以')'结尾
                int p = (i - 1) - dp[i - 1] - 1;
                if (s.charAt((i - 1) - 1) == '(') {  // 情况：...()
                    dp[i] = dp[i - 2] + 2;
                } else if (p >= 0 && s.charAt(p) == '(') {  // 情况：...((...))
                    dp[i] = 2 + dp[i - 1] + dp[i - dp[i - 1] - 2];
                }
                longest = Math.max(longest, dp[i]);
            }
        }
        return longest;
    }
}
